#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

import heapq


class Solution:
    """
    @param nums: A list of integers
    @return: the median of numbers
    """
    def medianII(self, nums):
        # and all left <= all right
        self.left_max_heap = []
        self.right_min_heap = []
        self.medians = []

        for v in nums:
            median = self.get_median_of_v(v)
            self.medians.append(median)

        return self.medians

    def get_median_of_v(self, value):
        # 放入左边
        heapq.heappush(self.left_max_heap, -value)

        # 左边最小值放入右边
        ele = heapq.heappop(self.left_max_heap)
        heapq.heappush(self.right_min_heap, -ele)

        # 调整个数: 保证相同. 或者左边比右边多一个
        if len(self.left_max_heap) < len(self.right_min_heap):
            ele = heapq.heappop(self.right_min_heap)
            heapq.heappush(self.left_max_heap, -ele)

        # 获取median
        # return -heapq.heaptop(self.left_max_heap)
        return -self.left_max_heap[0]


def main():
    print("start main")
    s = Solution()
    # s.medianII([4, 5, 1, 3, 2, 6, 0])
    s.medianII( [1, 2, 3, 4, 5] )
    print(s.medians)

if __name__ == "__main__":
    main()
